public class Solution76 {
    public String minWindow(String s, String t) {
        int[] f=new int[100];
        int[] g=new int[100];
        for (char c : t.toCharArray()) {
            f[c-'A']++;
        }
        for (char c : s.toCharArray()) {
            g[c-'A']++;
        }
        int dif=0;
        for (int i = 0; i < 100; i++) {
            if (f[i]>g[i]){
                return "";
            }
            if (f[i]!=0){
                dif++;
                g[i]=0;
            }
        }
        int min=Integer.MAX_VALUE;
        boolean flag=false;
        String ans=null;
        int j=0;
        for (int i=0;i<s.length();i++){
            g[s.charAt(i)-'A']++;
            if (g[s.charAt(i)-'A']==f[s.charAt(i)-'A']){
                dif--;
                if (dif==0 && !flag){
                    flag=true;
                }
            }
            if (flag){
                while (dif==0 && j<=i){
                    g[s.charAt(j)-'A']--;
                    if (g[s.charAt(j)-'A']+1==f[s.charAt(j)-'A']){
                        dif++;
                    }
                    j++;
                }
                if (i-j+2<min){
                    min=i-j+2;
                    ans=s.substring(j-1,i+1);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution76().minWindow("ADOBECODEBANC","ABC"));
    }
}
